package code;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Code217 {
	
	public void dfs(int step,int sum,List<List<Integer>> result,Stack<Integer> stack){
		if(step==0 && sum==0){
			List copyList=new ArrayList(stack);
			result.add(copyList);
			return ;
		}
		int i=stack.empty()?1:stack.peek()+1;
		for(;i<=9 && sum>=i;i++){
			if(stack.contains(i))
				continue;
			stack.push(i);
			dfs(step-1,sum-i,result,stack);
			stack.pop();
		}
	}
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        Stack<Integer> stack=new Stack<Integer>();
        dfs(k,n,result,stack);
        return result;
    }
    public static void main(String[] args){
    	new Code217().combinationSum3(3, 9);
    }
}
